package com.zk.algorithm.tree;

import com.zk.algorithm.bean.TreeNode;

/**
 * 前序和中序构建树
 *
 * preOrder=[3,9,20,15,7]
 * inOrder=[9,3,15,20,7]
 *
 * @author zk
 */
public class ConstructTreeWithPreAndInOrder {

    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
        return helper(0, 0, inOrder.length - 1, preOrder, inOrder);
    }

    private TreeNode helper(int preIndex,
                            int inStart, int inEnd,
                            int[] preOrder, int[] inOrder) {
        if ( preIndex >= preOrder.length ||
                (inStart > inEnd) ) {
            return null;
        }

        int rootVal = preOrder[preIndex];
        int rootIndex = findRootIndexInInOrder(rootVal, inStart, inEnd, inOrder);

        TreeNode root = new TreeNode(rootVal);
        // preOrder: [preIndex-                            preEnd]
        // inOrder: [inStart---------------root             inEnd]
        root.left = helper(preIndex + 1, inStart, rootIndex - 1, preOrder, inOrder);
        // preOrder: [preIndex                                            ]
        //           |<-  (rootIndex - inStart + 1) ->
        // preOrder: [                              preIndex              ]

        // inOrder: [inStart               root-------------inEnd]
        root.right = helper(preIndex + (rootIndex - inStart + 1), rootIndex + 1, inEnd, preOrder, inOrder);

        return root;
    }

    private int findRootIndexInInOrder(int rootVal, int inStart, int inEnd, int[] inOrder) {
        for (int i=inStart; i<=inEnd; i++) {
            if (inOrder[i] == rootVal) {
                return i;
            }
        }

        return -1;
    }

}
